Opciones de programación
Diseño específico de un lenguaje: Occam ? Transputer
Extensión de lenguaje existente: Fortran M, CC++, Cilk++
www.netlib.org/fortran-m
www-unix.mcs.anl.gov/dbpp/text/node51.html
www.cilk.com
Biblioteca de paso de mensajes sobre C, Fortran, C++
PVM: www.csm.ornl.gov/pvm
MPI: www-unix.mcs.anl.gov/mpi
HPC++: www.extreme.indiana.edu/hpc++/index.html
Paralelización automática: El compilador extrae
paralelismo del código secuencial
¿ Sistema
Operativo ?
OpenMP
(Gp:) 1979 Proyecto Europeo: Inmos SGS-Thomson ICL … †
(Gp:) Objetivo: µP de altas prestaciones, como elemento básico para
construir máquinas paralelas (multicomputadores)
(Gp:) 1992: habían vendido 500.000 unidades (µP+1MB => 180.000pts)
(Gp:) Característica relevante: 4 enlaces de comunicación (canales)
(Gp:) T800
(Gp:) 0
(Gp:) 1
(Gp:) 2
(Gp:) 3
Ejecución eficiente de n procesos que envían/reciben mensajes por canales
(Gp:) P1
(Gp:) P2
(Gp:) P3
Opciones … (TRANSPUTER)
(Gp:) cP3 ! dato
(Gp:) cP2 ? dato
Creación de procesos
¿Cómo podría ser contarPar.c si no hay memoria común?
(Gp:) 1
(Gp:) 3
(Gp:) 2
(Gp:) 2
(Gp:) 6 2 0 …
(Gp:) 0 6 7 …
(Gp:) 6 2 5 …
(Gp:) 2 1 7 …
(Gp:) +
(Gp:) 8
(Gp:) esclavo1
(Gp:) esclavo2
(Gp:) esclavo3
(Gp:) esclavo4
(Gp:) maestro
(Gp:) 6 2 0 …
(Gp:) 0 6 7 …
(Gp:) 6 2 5 …
(Gp:) 2 1 7 …
(Gp:) El vector lo tiene un proceso “maestro”
El maestro: reparte “envía” trabajo a los “esclavos” y
recoge “recibe” resultados
(Gp:) 6 2 0 …
(Gp:) 0 6 7 …
(Gp:) 6 2 5 …
(Gp:) 2 1 7 …
(Gp:) 1
(Gp:) 3
(Gp:) 2
(Gp:) 2
(Gp:) 2 tipos distintos de procesos
Creación de procesos
(Gp:) ¿Cómo podría ejecutarse la aplicación?
(Gp:) maestro
(Gp:) esclavo1
(Gp:) esclavo2
(Gp:) esclavoN
(Gp:) Un proceso x núcleo
(Gp:) M
(Gp:) E
(Gp:) E
(Gp:) E
Dos ejecutables: maestro.exe y esclavo.exe
(Gp:) maestro.c
(Gp:) esclavo.c
(Gp:) maestro.exe
(Gp:) esclavo.exe
(Gp:) Multiple Program Multiple Data
(Gp:) MPMD
(Gp:) maestro.exe
(Gp:) esclavo.exe
Creación de procesos: estática vs dinámica
¿Arquitecturas distintas?
¿ SPMD ?
Creación de procesos (creación dinámica)
MPMD: Multiple Program Multiple Data
(Gp:) —————————
spawn (“esclavo”, 4, …)
—————————
(Gp:) maestro.c
(Gp:) —————————
contarEnTrozo (……)
—————————
(Gp:) esclavo.c
(Gp:) maestro
(Gp:) esclavo
(Gp:) %pvm
pvm>add PC2 …..
pvm>spawn maestro
M
(Gp:) E
(Gp:) E
Creación de procesos (creación estática)
SPMD: Single Program Multiple Data
programa
fuente
(Gp:) *.exe
(Gp:) *.exe
(Gp:) *.exe
(Gp:) M
(Gp:) E
%mpirun –np 9 sort
%mpirun –p4pg
fiConf sort
(Gp:) —————————
if (miIdProceso == 0)
maestro()
else
esclavo()
—————————
(Gp:) sort.c
(Gp:) 0
(Gp:) 1
(Gp:) 8
Creación de procesos
A veces, viene bien que el maestro también trabaje
(Gp:) esclavo1
(Gp:) esclavo2
(Gp:) esclavo3
(Gp:) maestro0
(Gp:) 6 2 0 …
(Gp:) 0 6 7 …
(Gp:) 6 2 5 …
(Gp:) 2 1 7 …
(Gp:) 0 6 7 …
(Gp:) 6 2 5 …
(Gp:) 2 1 7 …
(Gp:) 1
(Gp:) 3
(Gp:) 2
(Gp:) 2
Modelo SPMD y creación de procesos estática
Rutinas genéricas de paso de mensajes
Pi.enviar(Pj, &msj, …) ? Pj.recibir(Pi, &msj, …)
(Gp:) —————————
enviar (esclavo,
&rodaja[k], …)
—————————
(Gp:) sortM
(Gp:) —————————
recibir (maestro,
&miRodaja, …)
—————————
(Gp:) sortE
(Gp:) Máquina
PID_Local
Varias semánticas:
Bloqueante (Síncrona | Rendezvous)
No bloqueante (Asíncrona: Capacidad de almacenar)
Temporizada (Tiempo máximo de bloqueo)
(Gp:) enviar( Pi, &msj, temporización, )
(Gp:) ?
(Gp:) 0
(Gp:) t
Rutinas genéricas de paso de mensajes
Bloqueante vs NoBloqueante
(Gp:) ———-
———-
enviar…
———-
———-
(Gp:) ———-
———-
recibir…
———-
———-
(Gp:) El primero se bloquea
(Gp:) Transferencia sin buffers adicionales
(Gp:) Se sabe que se ha recibido
(Gp:) ———-
———-
enviar…
———-
———-
(Gp:) ———-
———-
recibir…
———-
———-
(Gp:) Buffer
(Gp:) Se desacopla env | rec
(Gp:) Gestión de buffers
(Gp:) ¿ Dónde ?
(Gp:) ¿Se ha recibido? => msjACK
enviar( Pi, &msj, temporización, …)
Rutinas genéricas de paso de mensajes
recibirDeCualquiera (&msj) | recibir ( -1, &msj)
(Gp:) sortE1
(Gp:) sortEn
(Gp:) sortM
(Gp:) —————————
quien = recibir (-1,
&rodaja[k], …)
—————————
(Gp:) sortM
Mensajes etiquetados
P
P
P
P
P
P
P
H
(Gp:) enviar (S, &msj, tipoP)
enviar (S, &msj, tipoH)
(Gp:) recibir (-1, &msj, tipoH)
recibir (-1, &msj, -1 )
(Gp:) Cliente
(Gp:) Servidor
(Gp:) Cliente
(Gp:) Cliente
Paso de mensajes entre “grupos”
Broadcast (a todos) Multicast (a unos concretos)
(Gp:) —————————
Para todo esclavo
enviar (esclavo,
&palabra, …)
—————————
(Gp:) cuentaM
Problema: Número de ocurrencias de (un dato)* en array grande
(Gp:) cuentaM
(Gp:) cuentaE1
(Gp:) cuentaEn
(Gp:) cuentaE2
(Gp:) “Ala”
(Gp:) “Ala”
(Gp:) “Ala”
(Gp:) —————————
bcast (esclavos,
&palabra, …)
—————————
(Gp:) cuentaM
¿Más eficiente?
¿Sincronismo?
(Gp:) sortM
(Gp:)
sortE1
(Gp:)
sortEn
(Gp:) V
(Gp:) sortM
(Gp:)
sortE1
(Gp:)
sortEn
(Gp:) V
Paso de mensajes entre “grupos”
scatter ( esparcir ) y gather ( recoger ) Ej: Ordenación
(Gp:) scatter (V, rodaja, grupo, emisor, )
(Gp:) sortM y sortE
(Gp:) gather (V, rodaja, grupo, receptor, )
(Gp:) sortM y sortE
Paso de mensajes entre “grupos”
int V[N];
inic(V);
i=0;
for (e=1; e< =nProc; e++) {
enviar (e, &V[i], longRodaja);
i += longRodaja;
}
ordenar (V, longRodaja);
i=0;
for (e=1; e< =nProc; e++) {
recibir(e, &V[i], longRodaja);
i += longRodaja;
}
int R[longRodaja];
recibir (0, R, longRodaja);
ordenar (V, longRodaja);
enviar (0, R, longRodaja);
int *V;
if (yo==0) { V = malloc(N); inic(V); }
else V = malloc(longRodaja);
scatter (V, V, grupo, 0);
ordenar (V, longRodaja);
gather (V, V, grupo, 0);
(Gp:) cuentaM
(Gp:)
cuentaE1
(Gp:) 2
(Gp:) 3
(Gp:)
cuentaE2
(Gp:) 5
(Gp:)
cuentaEn
(Gp:) 1
Paso de mensajes entre “grupos”
reduce (recibir de unos concretos y operar) Ej: Ocurrencias
(Gp:) Total = veces;
Para todo esclavo
recibir (esclavo,
&veces, …)
Total += veces;
(Gp:) cuentaM
(Gp:) reduce (+, &veces, grupo, receptor, …)
(Gp:) cuentaM y cuentaE
(Gp:) +
(Gp:) máximo, mínimo, *, …..
¿Más eficiente?
MPI (Introducción)
MPI: Message Passing Interface – 1994 MPI Forum [Nov/92]
“Ejecución de aplicaciones paralelas distribuidas en ordenadores heterogéneos”
(Gp:) maestro
(Gp:) esclavo1
(Gp:) esclavo3
(Gp:) esclavo2
(Gp:) esclavo4
Cada uno con su dirIP
Biblioteca “mpi.h”
MPI_Send,
MPI_Recv,
————-
(Gp:) M
(Gp:) E1
(Gp:) E2
(Gp:) E3
(Gp:) E4
Implementación
MPICH
LAM/MPI
IBM, …
MPI-2
MPI-3
(Gp:) >= 0 => MPI_SUCCESS, significado concreto
< 0 => un error ( … MPI_ERR_ARG …)
MPI (Procesos)
(Gp:) int MPI_Comm_size(…, int *numProcesos);
(Gp:) int MPI_Comm_rank(…, int *yo);
(Gp:) int MPI_Finalize();
(Gp:) int MPI_Init( ……. ); /* Inicia MPI */
Creación estática de procesos (según implementación “mpirun”)
(Gp:) 0
(Gp:) 1
(Gp:) 3
(Gp:) 2
(Gp:) 4
(Gp:) MPI_COMM_WORLD
2
(Gp:) 5
(Gp:) 2
MPI (Procesos)
(Gp:) helloWorld paralelo
(Gp:) #include “mpi.h”
int main (int argc,
char *argv[]) {
int yo, numProcesos;
MPI_Init (&argc, &argv);
MPI_Comm_size (MPI_COMM_WORLD, &numProcesos);
MPI_Comm_rank (MPI_COMM_WORLD, &yo);
if (yo == 0) printf (“Creados %d procesosn”, numProcesos);
printf (“Hola, soy el proceso %dn”, yo);
MPI_Finalize();
}
% mpirun –np 3 helloWorld
% mpirun –p4pg helloWorld.txt helloWorld
(Gp:) pc1 2 /usuarios/alumnosPropar/propar01/p1/helloWorld
pc2 2 /usuarios/alumnosPropar/propar01/p1/helloWorld
pc3 1 /usuarios/alumnosPropar/propar01/p1/holaMundo
MPI (Envío y Recepción Simple)
Enviar y recibir arrays de datos simples (int, byte, …) Bloqueante
int vector[N];
———-
MPI_Send (vector, …
P2, …)
———-
P1
int tabla[M];
———-
MPI_Recv (tabla, …
P1, …)
———-
P2
int MPI_Send(void *buffer, int cuantos, MPI_Datatype tipo,
int destino, int etiqueta, MPI_Comm grupo)
(Gp:) MPI_INT,
MPI_FLOAT, …
(Gp:) MPI_COMM_WORLD
(Gp:) 0..MPI_TAG_UB
MPI (Envío y Recepción Simple)
Enviar y recibir arrays de datos simples (int, byte, …) Bloqueante
int MPI_Recv(void *buffer, int cuantos, MPI_Datatype tipo,
int remitente,int etiqueta,MPI_Comm grupo,
MPI_Status *estado)
(Gp:) estado.MPI_SOURCE
estado.MPI_TAG
(Gp:) MPI_ANY_SOURCE
(Gp:) MPI_ANY_TAG
(Gp:) int MPI_Get_count( MPI_Status *estado, MPI_Datatype tipo,
int *cuantos)
MPI (Envío y Recepción Simple)
Ejemplo de uso: psendrec.c
#include < stdio.h>
#include < unistd.h>
#include “mpi.h"
#define N 3
#define VECES 5
void esclavo(void) {…}
void maestro(void) {…}
int main( int argc, char *argv[] ) {
int yo;
MPI_Init (&argc, &argv);
MPI_Comm_rank (MPI_COMM_WORLD, &yo);
if (yo == 0) maestro();
else esclavo();
MPI_Finalize();
return 0;
}
MPI (Envío y Recepción Simple)
Ejemplo de uso: psendrec.c
void maestro (void) {
int i, j, vector[N];
for (i=0; i< VECES; i++) {
printf ("M: envia => ");
for (j=0; j< N; j++) {
vector[j] = i*N+j;
printf("%d ", vector[j]);
}
printf ("n");
MPI_Send (vector, N, MPI_INT, 1, 1, MPI_COMM_WORLD);
}
}
(Gp:) esclavo
MPI (Envío y Recepción Simple)
Ejemplo de uso: psendrec.c
void esclavo(void) {
int i, j,tabla[N], n;
MPI_Status estado;
sleep(2);
for (i=0; i< VECES; i++) {
MPI_Recv (tabla, N, MPI_INT, 0, 1,
MPI_COMM_WORLD, &estado);
MPI_Get_count (&estado, MPI_INT, &n);
printf ("E: recibe => ");
for (j=0; j< N; j++) printf("%d ", tabla[j]);
printf (" de tid = %d eti = %d longi = %dn",
estado.MPI_SOURCE, estado.MPI_TAG, n);
}
}
(Gp:) maestro
MPI (Envío y Recepción No Tan Simple)
int MPI_Iprobe(int origen, int etiqueta, MPI_Comm grupo, int *hayMsj, MPI_Status *estado)
Enviar y recibir arrays de datos simples No Bloqueante
Enviar y recibir datos no homogéneos
Crear tipos => Algo tedioso
(Gp:) Hacer otras cosas
(Gp:) NO
(Gp:) int MPI_Recv(void *buffer,… MPI_Status *estado)
(Gp:) SI
MPI (Comunicación colectiva)
int MPI_Bcast(void *buffer, int cuantos,
MPI_Datatype tipo, int emisor,
MPI_Comm grupo)
(Gp:) cuenta.0
(Gp:) cuenta.1
(Gp:) cuenta.N
(Gp:) cuenta.2
(Gp:) “Ala”
(Gp:) “Ala”
(Gp:) “Ala”
void maestro () { void esclavo () {
char palabra[4]; char texto[4];
———- ———-
MPI_Bcast ( MPI_Bcast (
palabra, 4, MPI_CHAR, texto, 4, MPI_CHAR,
0, MPI_COMM_WORLD); 0, MPI_COMM_WORLD);
———- ———-
(Gp:) ?
(Gp:) tag
(Gp:) Send+Recv
MPI (Comunicación colectiva)
int MPI_Scatter(
void *vOrg, int nOrg, MPI_Datatype tOrg,
void *vDst, int nDst, MPI_Datatype tDst,
int emisor, MPI_Comm grupo);
(Gp:)
grupoE.1
(Gp:)
grupoE.9
(Gp:) grupoM.0
int MPI_Reduce(void *vOrg, void *vDst, int nOrg,
MPI_Datatype tDatoOrg, int operacion,
int receptor, MPI_Comm grupo);
(Gp:) +
(Gp:) MPI_SUM, MPI_PROD, MPI_MIN, MPI_MAX, ….
(Gp:) sendCount
MPI (Comunicación colectiva: Ejemplo)
Ejemplo de uso completo: cuentaPar2.c (modelo SPMD)
#include < stdio.h>
#include “mpi.h"
#define CARDINALIDAD 2000000
#define MAX_ENTERO 1000
#define NUM_BUSCADO 5
int main( int argc, char *argv[] ) {
int i, numVeces, numVecesTotal, yo;
int longRodaja, numProcesos;
int *vector;
MPI_Init (&argc, &argv);
MPI_Comm_size (MPI_COMM_WORLD, &numProcesos);
MPI_Comm_rank (MPI_COMM_WORLD, &yo);
—————————
MPI_Finalize();
}
MPI (Comunicación colectiva: Ejemplo)
Ejemplo de uso completo: cuentaPar2.c
// Pedir memoria vector e inicializarlo si maestro
longRodaja = CARDINALIDAD / numProcesos;
if (yo == 0) {
vector = malloc (CARDINALIDAD * 4);
for (i=0; i< CARDINALIDAD; i++)
vector[i] = random() % MAX_ENTERO;
} else
vector = malloc (longRodaja * 4);
MPI_Scatter (vector, longRodaja, MPI_INT,
vector, longRodaja, MPI_INT, 0, MPI_COMM_WORLD);
// Todos buscan en su trozo
numVeces = 0;
for (i=0; i< longRodaja; i++)
if (vector[i] == NUM_BUSCADO) numVeces++;
MPI_Reduce (&numVeces, &numVecesTotal, 1, MPI_INT,
MPI_SUM, 0 , MPI_COMM_WORLD);
if (yo == 0)
printf (“Numero de veces => %dn”, numVecesTotal);
MPI (Comunicación colectiva)
Otras llamadas interesantes:
int MPI_Gather(void *vOrg, int nOrg, MPI_Datatype tOrg,
void *vDst, int nDst, MPI_Datatype tDst,
int receptor, MPI_Comm grupo);
int MPI_Barrier(MPI_Comm grupo);
———-
MPI_Comm_size (MPI_COMM_WORLD, &numProcesos);
———-
// Computar todos paso 1
MPI_Barrier (MPI_COMM_WORLD);
// Computar todos paso 2
(Gp:) 6
Evaluación de programas paralelos
¿Cuánto tardará mi programa paralelo TP?
Medición experimental
Estudio analítico
(Gp:) Codificar, Depurar, Probar, …
(Gp:) Modelo imperfecto, aproximado
(Gp:) m
(Gp:) e0
(Gp:) e9
(Gp:) cuentaVeces:
V[1.000.000]
10 esclavos
(Gp:) TP = TCPU + TRED
(Gp:) Enviar rodajas TRED
(Gp:) Recibir veces TRED
(Gp:) Contar veces TCPU
(Gp:) veces = 0;
for (i=0; i< N’; i++)
if (rodaja[i] == D)
veces++;
(Gp:) N’
(Gp:) N
(Gp:) N’ * (#i * Tinst)
(Gp:) O (N)
| O (N2) | O (NlogN) | O(logN)
Evaluación de programas paralelos
(Gp:) #m * (TL + #d * TD)
(Gp:) #d
(Gp:) t
(Gp:) TL
(Gp:) TP = TCPU + TRED
(Gp:) N’ * (#i * Tinst)
(Gp:) Ejemplos
(Gp:) T3D+PVM
(Gp:) IBM PS2+MPI
(Gp:) iacluster+MPI
(Gp:) 40?s
(Gp:) 35?s
(Gp:) 3?s
(Gp:) TL
(Gp:) 64ns
(Gp:) 230ns
(Gp:) 63ns
(Gp:) TD[8B]
(Gp:) 0,6ns
(Gp:) 4,2ns
(Gp:) 11ns
(Gp:) Tinst
(Gp:) 66666
(Gp:) 8333
(Gp:) 273
(Gp:) TL
(Gp:) 107
(Gp:) 55
(Gp:) 6
(Gp:) TD
(Gp:) 1
(Gp:) 1
(Gp:) 1
(Gp:) Tinst
(Gp:) Normalizar
(Gp:) TP = TCPU + TRED
(Gp:) Solapar tiempos | ocultar latencias
Comunicación asíncrona
(Gp:) #msj,
tamaño(#d),
topología red,
tecnología, …
Evaluación de programas paralelos
Ejemplo: cuentaVeces, V[1.000.000], 10 esclavos
T1 = 1.000.000 * (#i * Tinst)
T10 = TRED(10Rodajas) + TCPU(100.000) + TRED(10Resultados)
(Gp:) T3D: TL(273) y TD(6)
(Gp:) T10 = 10*(273+100.000*6) + 100.000*#i*1 + 10*(273+6)
= 6.005.520 + 100.000#i
S10 = 1.000.000*#i / (6.005.520+100.000#i)
(Gp:) iacluster: TL(66.666) y TD(64)
(Gp:) T10 = … 66.666 … 64 + …*1 + … 66.666+64
= 65.333.960 + 100.000#i
S10 = 1.000.000*#i / (65.333.960 +100.000#i)
(Gp:) #i
(Gp:) S10
(Gp:) 50
(Gp:) 0,71
(Gp:) 100
(Gp:) 1,33
(Gp:) 500
(Gp:) 4,34
(Gp:) #i
(Gp:) S10
(Gp:) 5
(Gp:) 0,8
(Gp:) 10
(Gp:) 1,4
(Gp:) 500
(Gp:) 8,9
Herramientas de depuración y monitorización
Medición de tiempos de ejecución
Depuración
Monitorización
(Gp:) #include < sys/time.h>
struct timeval t0, tf, tiempo;
/* Inicialización */
gettimeofday (&t0, NULL);
/* ejecucion del programa paralelo */
gettimeofday (&tf, NULL);
timersub (&tf, &t0, &tiempo);
printf (“Tiempo => %ld:%ld seg:micron”,
tiempo.tv_sec, tiempo.tv_usec);
(Gp:) Evitar E/S
¿Efecto del
optimizador
de código?
gcc –O3
Herramientas de depuración y monitorización
(Gp:) %mpirun –dbg=ddd –np 2 psendrec
Depurar más de un proceso, algo más complejo
printf
fflush(stdout)
setbuf(stdout,
NULL)
(Gp:) depurar (ddd)
Herramientas de depuración y monitorización
Monitorización (XPVM) para PVM
Herramientas de depuración y monitorización
Monitorización (totalview) para MPI, openMP, … www.etnus.com
(Gp:) www.roguewave.com
 Página anterior | Volver al principio del trabajo | Página siguiente  |